//
// Created by Martin on 2022/4/8.
//
#ifdef __GUNC__
#include <bits/stdc++.h>

#else
#include <vector>
#include <iostream>

#endif // __GUNC__


using namespace std;

//------------------------------------------------------
// 二叉树搜索 BinarySearchTree

/**
  Definition for a binary tree node.
  */
template<typename T>
struct TreeNode {
    T val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(T x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(T x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

template<typename T>
class BSTree {
public:
    TreeNode<T>* searchBST(TreeNode<T>* root, T key) { // 二叉查找树递归查找
        if ((!root) || key == root->val) {
            return root;
        }
        else if (key < root->val) {
            return searchBST(root->left, key); // 在左子树中查找
        }
        else {
            return searchBST(root->right, key); // 在右子树中查找
        }
    }

    void insertBST(TreeNode<T>*& root, T e) { // 二叉树的插入
        if (!root) {
            TreeNode<T>* s = new TreeNode<T>(e); // 生成新节点
            root = s; // 将新节点s连接到已经找到的插入位置
        }
        else if (e < root->val) {
            insertBST(root->left, e);  // 插入左子树中
        }
        else {
            insertBST(root->right, e); // 插入右子树中
        }
    }

    void createBST(TreeNode<T>*& root) {
        root = nullptr;
        T e;
        while (cin >> e) {
            insertBST(root, e);
        }
    }

    void deleteBST(TreeNode<T>*& root, T key) {
        TreeNode<T>* p = root;
        TreeNode<T>* f = nullptr;
        TreeNode<T>* q;
        TreeNode<T>* s;

        if (!root) return;
        while (p) { // 查找
            if (p->val == key) break; // 找到关键字等于key的节点p, 结束循环
            f = p; // f为p双亲
            if (p->val > key) {
                p = p->left;
            }
            else {
                p = p->right;
            }
        }

        if (!p) return; // 找不到被删除节点则返回
        // 三种情况: p左右子树均不为空, 无右子树, 无左子树
        if (p->left && p->right) {
            q = p;
            s = p->left;
            while (s->left) { // 在p左子树中查找p的前驱s, 即最右下节点
                q = s; // q是s父节点
                s =s->right;
            }
            p->val = s->val; // 将s的值赋给被删除节点p, 然后删除s
            if (q != p) {
                q->right = s->right; // 重接q右子树
            }
            else {
                q->left = s->left;   // 重接q左子树
            }
            delete s;
        }
        else {
            if (!p->right) { // 被删节点p无右子树, 只需重接左子树
                q = p;
                p = p->left;
            }
            else if (!p->left) { // 被删节点p无左子树, 只需重接右子树
                q = p;
                p = p->right;
            }

            // 将p所指子树挂接到其双亲f相应的位置
            if (!f) {
                root = p; // 被删节点是根节点
            }
            else if (q == f->left) {
                f->left = p; // 挂接到f左子树
            }
            else {
                f->right = p; // 挂接到f右子树
            }
            delete q;
        }
    }
};

class Solution {
public:
    TreeNode<int>* sortedArrayToBST(vector<int>& nums) {
        int len = nums.size();
        return dfs(nums, 0, len);
    }
    
    TreeNode<int>* dfs(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int mid = left + (right - left) / 2;
        TreeNode<int>* root = new TreeNode<int>(nums[mid]);
        root->left = dfs(nums, left, mid - 1);
        root->right = dfs(nums, mid + 1, right);
        return root;
    }
};

//------------------------------------------------------
// test

int main()
{
    return 0;
}